
UTIL_LOADED = false -- force reload
if (not exists) or (not exists("UTIL_LOADED")) or (not UTIL_LOADED) then
UTIL_LOADED = true

--assert(getmetatable(_G)==nil, "_G already has a metatable")
--setmetatable(_G, { __index = function(t, i) error("attempt to index nil global "..i, 2) end })
function exists(k) return rawget(_G, k)~=nil end

function islist(t) local n = 0; for i, v in pairs(t) do if type(i)~="number" or i%1~=0 then return false end; n = n+1; end; return n==#t; end
function range(a, b, c) if b then local inc = c or 1; local i = a-inc; return function() i = i+inc; if i>b then return nil else return i end; end; else return range(1, a) end end
function map(t, f) local u = {}; for i, v in ipairs(tolist(t)) do u[i] = f(v) end; return u; end
function mapi(t, f) local u = {}; for i, v in ipairs(tolist(t)) do u[i] = f(i, v) end; return u; end
function each(t) t = tolist(t); local i = 0; return function() i = i+1; return t[i]; end; end
function tolist(g) local t = type(g); if t=="table" then return g elseif t=="function" then local u = {}; for v in g do table.insert(u, v) end; return u; else error("list: invalid type "..t); end end
function reverse(t) local u = {}; for i = #t, 1, -1 do table.insert(u, t[i]) end; return u; end
--function copy(t) local u = {}; for v in each(t) do table.insert(u, v) end; return u; end
function copy(t) if type(t)=="table" then local u = {}; for k, v in pairs(t) do u[k] = copy(v) end; return u; else return t end end
function takerandom(l) local i = math.random(1, #l); local v = l[i]; table.remove(l, i); return v; end
function takelast(l) local v = l[#l]; table.remove(l, #l); return v; end
function takefirst(l) local v = l[1]; table.remove(l, 1); return v; end
function getrandom(l) return l[math.random(1, #l)] end
function take(t, i) local v = t[i]; table.remove(t, i); return v; end
function flip(t) local u = {}; for i, v in pairs(t) do u[v] = i end; return u; end
function string.bytes(s) return map(s:split(), string.byte) end
function string.hex(s) return map(s:bytes(), function(x) return string.format("%02X", x) end) end
function string.bits(s) local u = {}; for b in each(s:bytes()) do for p = 1, 8 do table.insert(u, bit.band(bit.rshift(b, 8-p), 1)) end end; return u; end
--function expand(t) local u = {}; for st in each(t) do for sst in each(st) do table.insert(u, sst) end end; return u; end
--function pad(t, n, v) local u = copy(t); for i = #u+1, n do u[i] = v end; return u; end
function pick(t, u) local w = {}; for k, v in pairs(t) do if u[k]~=nil then w[k] = u[k] else w[k] = v end end; return w; end
--function curry(f, ...) local va = {...}; return function(v) return f(v, unpack(va)) end; end
function tsub(t, a, b) local u = {}; for i = a, b do u[i-a+1] = t[i] end; return u; end
--function apply(t, f) local v = t[1]; for i = 2, #t do v = f(v, t[i]) end; return v; end
function map2(t1, t2, f) t1 = tolist(t1); t2 = tolist(t2); local u = {}; assert(#t1==#t2, "map2: argument lists are different lengths"); for i, v in ipairs(t1) do u[i] = f(v, t2[i]) end; return u; end
function mapd(t, f) local u = {}; for k, v in pairs(t) do u[k] = f(v) end; return u; end
function mapdi(t, f) local u = {}; for k, v in pairs(t) do u[k] = f(k, v) end; return u; end
function insert(t, v, i) if v==nil then return end; if i then table.insert(t, i, v) else table.insert(t, v) end; return v; end
--function call(f) return f() end
function insertall(t, u) for v in each(u) do insert(t, v) end; end
function append(t, x) local u = copy(t); table.insert(u, x); return u; end
function all(t, f) for v in each(t) do if not f(v) then return false end end; return true; end
function none(t, f) for v in each(t) do if f(v) then return false end end; return true; end
function any(t, f) for v in each(t) do if f(v) then return true end end; return false; end
function first(t, f) for v in each(t) do if f(v) then return v end end; return nil; end
function randomorder(t) local u = {}; local o = tolist(range(#t)); while #o>0 do insert(u, t[takerandom(o)]) end; return u; end

function vectoradd(a, b) assert(#a==#b); return map(range(#a), function(i) return a[i]+b[i] end); end
function vectorsub(a, b) assert(#a==#b); return map(range(#a), function(i) return a[i]-b[i] end); end
function vectormul(a, b) assert(#a==#b); return map(range(#a), function(i) return a[i]*b[i] end); end
function vectorscale(a, x) return map(a, function(n) return x*n end) end
function vectorlen(a) local s = 0; map(a, function(n) s = s+(n*n) end); return math.sqrt(s); end
function vectorfromstr(s) return map(s:split(" "), tonumber) end
function vecfromstr(s) return map(s:split(" "), tonumber) end
function vectortostr(v) return table.concat(v, " ") end
function vectostr(v) return table.concat(v, " ") end
function vectorequal(a, b, t) assert(#a==#b); for i=1, #a do if math.abs(a[i]-b[i])>(t or 0) then return false end end; return true; end
function vectordist(a, b) return vectorlen(vectorsub(a, b)) end

function xor(a, b) return (not a)~=(not b) end

local function concatlist(l) return table.concat(map(l, tostring), "\t") end
local function listtostring(t) local u = {}; for i, v in ipairs(t) do u[i] = tostring(v) end; return "{"..table.concat(u, ", ").."}"; end
local old_tostring = tostring; function tostring(v) if type(v)=="table" and islist(v) then return listtostring(v) else return old_tostring(v) end end
function printtab(d, ...) print(("  "):rep(d)..concatlist({...})) end

-- split string into table by separator
function string.split(s, sep, regex)
	if type(s)~="string" then error("string.split: expected string at argument 1, got "..type(s)) end
	if sep==nil or sep=="" then
		local t = {}
		local ns = #s
		for x = 1, ns do
			table.insert(t, s:sub(x, x))
		end
		return t
	elseif type(sep)=="string" then
		local t = {}
		if #s>0 then
			local first = 1
			while true do
				local last, newfirst = s:find(sep, first, regex)
				if not last then break end
				table.insert(t, s:sub(first, last-1))
				first = newfirst+1
			end
			table.insert(t, s:sub(first, #s))
		end
		return t
	else
		error("string.split: expected nil or string at argument 2, got "..type(sep))
	end
end

function string.trim(s)
	return s:gsub("^[ \r\n\t]+", ""):gsub("[ \r\n\t]+$", "")..""
end

function string.getpath(s) return (s:match("([.+])[\\/][^\\/]+$") or error("could not get path of \""..s.."\"")).."" end
function string.getname(s) return (s:match("[^\\/]+$") or error("could not get name of \""..s.."\"")).."" end

-- read entire file at once, return nil if access failed
function io.readall(filename)
	local fi = io.open(filename, "rb")
	if not fi then return nil end
	local s = fi:read("*a")
	fi:close()
	return s
end

-- write data to file all at once, return true if success / false if failure
function io.writeall(filename, data)
	local fi = io.open(filename, "wb")
	if not fi then return false end
	fi:write(data)
	fi:close()
	return true
end

function string.escape(s)
	return s -- todo
end
local function tostringval(v)
	local t = type(v)
	if     t=="table"  then return tostring(v)
	elseif t=="string" then return "\""..v:escape().."\""
	else                    return tostring(v) end
end
local function toidx(k)
	if type(k)=="string" and k:find("^[a-zA-Z0-9_]+$") then return k
	else return "["..tostringval(k).."]" end
end
function tabletostring(t, splitlines, tabs, seen) tabs = tabs or 0; seen = seen or {};
	local il = islist(t)
	if t.__type == "vector" then splitlines = false end
	local s = "{"..(splitlines and "\n" or " ")
	local nonempty = false
	for k, v in pairs(t) do
		nonempty = true
		s = s..(splitlines and (("    "):rep(tabs+1)) or "")..(il and "" or (toidx(k).." = "))
		if type(v)=="table" then
			if seen[v] then
				s = s..tostring(v)
			else
				seen[v] = true
				s = s..tabletostring(v, splitlines, tabs+1, seen)
			end
		else s = s..tostringval(v) end
		s = s..(splitlines and ",\n" or ", ")
	end
	if nonempty and (not splitlines) then s = s:sub(1, #s-2).." " end -- remove trailing comma
	if(not nonempty) then s = s:sub(1, #s-1) end -- convert { } to {}
	s = s..(splitlines and nonempty and (("    "):rep(tabs).."}") or "}")
	return s
end

function printt(t) if type(t)=="table" then print(tabletostring(t)) else print(t) end end
function printtl(t) if type(t)=="table" then print(tabletostring(t, true)) else print(t) end end

function string.findall(s, p) local t = {}; for m in s:gmatch(p) do table.insert(t, m) end; return t; end

function wideset(t, v, ...)
	local keys = {...}; local nk = #keys; local lk = keys[nk];
	for i = 1, nk-1 do local k = keys[i];
		if not t[k] then t[k] = {} end; t = t[k];
	end
	t[lk] = v;
end
function wideget(t, ...)
	local keys = {...}; local nk = #keys;
	for i = 1, nk do t = t[keys[i]]; if t==nil then return nil end; end
	return t
end
function wideinsert(t, v, ...)
	local keys = {...}; local nk = #keys; local lk = keys[nk];
	for i = 1, nk do local k = keys[i];
		if not t[k] then t[k] = {} end; t = t[k];
	end
	table.insert(t, v)
end
function wideeach(t, l)
	if l==1 then
		local p = pairs(t)
		local k, v
		return function()
			k, v = p(t, k)
			return k, v
		end
	else
		local p = wideeach(t, 1)
		
		local k, v = p()
		local w = wideeach(v, l-1)
		local iter
		iter = function()
			local v2 = {w()}
			if v2[1] then
				return k, unpack(v2)
			else
				k, v = p()
				if k then
					w = wideeach(v, l-1)
					return iter()
				else
					return nil
				end
			end
		end
		return iter
	end
end

function math.round(x) return math.floor(x+0.5) end
function math.mod(x, m) return ((x/m)-math.floor(x/m))*m end
function math.clamp(v, n, x) return math.min(x, math.max(v, n)) end

local function grab_byte(v)
	return math.floor(v / 256), string.char(math.floor(v) % 256)
end
function string.fromFloat(x)
	local sign = 0
	if x < 0 then sign = 1; x = -x end
	local mantissa, exponent = math.frexp(x)
	if x == 0 then -- zero
		mantissa = 0; exponent = 0
	else
		mantissa = (mantissa * 2 - 1) * math.ldexp(0.5, 24)
		exponent = exponent + 126
	end
	local v, byte = "" -- convert to bytes
	x, byte = grab_byte(mantissa); v = v..byte -- 7:0
	x, byte = grab_byte(x); v = v..byte -- 15:8
	x, byte = grab_byte(exponent * 128 + x); v = v..byte -- 23:16
	x, byte = grab_byte(sign * 128 + x); v = v..byte -- 31:24
	return v
end
function string.toFloat(x)
	local sign = 1
	local mantissa = string.byte(x, 3) % 128
	for i = 2, 1, -1 do mantissa = mantissa * 256 + string.byte(x, i) end
	if string.byte(x, 4) > 127 then sign = -1 end
	local exponent = (string.byte(x, 4) % 128) * 2 + math.floor(string.byte(x, 3) / 128)
	if exponent == 0 then return 0 end
	mantissa = (math.ldexp(mantissa, -23) + 1) * sign
	return math.ldexp(mantissa, exponent - 127)
end

function memoize(f)
	local t = {}
	return function(a)
		if not t[a] then t[a] = f(a) end
		return t[a]
	end
end

function memoize_multiarg(f)
	local t = {}
	return function(...)
		local v = wideget(t, ...)
		if not v then
			v = f(a)
			wideset(t, v, ...)
		end
		return v
	end
end

function memoize_multiarg_multiret(f)
	local t = {}
	return function(...)
		local v = wideget(t, ...)
		if not v then
			v = {f(a)}
			wideset(t, v, ...)
		end
		return unpack(v)
	end
end

local base64Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
local base64Vals = {}
for i = 1, 64 do base64Vals[base64Chars:sub(i, i)] = i-1 end
function encodeBase64(v, n)
	local b = {}
	assert(v<64^n, "encodeBase64: number too big")
	for i = n-1, 0, -1 do
		local p = 64^i
		local d = math.floor(v/p)
		v = v - d*p
		table.insert(b, base64Chars:sub(d+1, d+1))
	end
	assert(#b==n)
	return table.concat(b)
end
function decodeBase64(s)
	local v = 0
	for i = 1, #s do
		v = v + base64Vals[s:sub(i, i)]*(64^(#s - i))
	end
	return v
end

require("class")
require("vector")

ENV_TS = exists("ts")
if ENV_TS then
	require("tsutil")
else
	ts = {
		eval = function() end,
		call = function() end,
		callobj = function() end,
		get = function() end,
		getobj = function() end,
		set = function() end,
		setobj = function() end,
		allBricks = function() return function() return nil end end,
	}
end

function inBox(x, y, bx, by, bw, bh)
	return x>=bx and y>=by and x<=bx+bw and y<=by+bh
end

function table.export(t)
	local st = {}
	for k, v in pairs(t) do
		table.insert(st, k.."\t"..v.."\n")
	end
	return table.concat(st)
end
function table.import(s)
	local t = {}
	for k, v in s:gmatch("([^\r\n]+)\t([^\r\n]+)") do
		t[k] = v
	end
	return t
end

end
